package com.sheng.leetcode.year2022.month04.day22;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/04/22
 *
 * 396. 旋转函数
 *
 * 给定一个长度为 n 的整数数组 nums 。
 *
 * 假设 arrk 是数组 nums 顺时针旋转 k 个位置后的数组，
 * 我们定义 nums 的 旋转函数  F 为：
 *
 * F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1]
 * 返回 F(0), F(1), ..., F(n-1)中的最大值 。
 *
 * 生成的测试用例让答案符合 32 位 整数。
 *
 * 示例 1:
 *
 * 输入: nums = [4,3,2,6]
 * 输出: 26
 * 解释:
 * F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
 * F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
 * F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
 * F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
 * 所以 F(0), F(1), F(2), F(3) 中的最大值是 F(3) = 26 。
 * 示例 2:
 *
 * 输入: nums = [100]
 * 输出: 0
 *
 * 提示:
 *
 * n == nums.length
 * 1 <= n <= 105
 * -100 <= nums[i] <= 100
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/rotate-function
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0396 {

    @Test
    public void test01(){
        int[] nums = {4,3,2,6};
        System.out.println(new Solution().maxRotateFunction(nums));
    }

}
//class Solution {
//    public int maxRotateFunction(int[] nums) {
//        int length = nums.length;
//        int max = max(length, nums);
//        //i代表F(X)，里面的X
//        for (int i = 1; i < length; i++) {
//            //n代表从第n个位置开始进行计算
//            int n = length - i;
//            //循环计算F(X)的值
//            int count = max(n, nums);
//            if (max < count) {
//                max = count;
//            }
//        }
//        return max;
//    }
//
//    public int max(int n, int[] nums) {
//        int count = 0;
//        //循环计算F(X)的值
//        for (int j = 0; j < nums.length; j++) {
//            if (n >= nums.length) {
//                n = 0;
//            }
//            count += j * nums[n];
//            n++;
//        }
//        return count;
//    }
//}

class Solution {
    public int maxRotateFunction(int[] nums) {
        int n = nums.length;
        int[] sum = new int[n * 2 + 10];
        for (int i = 1; i <= 2 * n; i++) {
            sum[i] = sum[i - 1] + nums[(i - 1) % n];
        }
        int ans = 0;
        //将F(0)的结果赋值给ans
        for (int i = 1; i <= n; i++) {
            ans += nums[i - 1] * (i - 1);
        }
        //滑块思想，每次前去前面的值，加上后面的值，如果比最大值大则进行赋值
        for (int i = n + 1, cur = ans; i < 2 * n; i++) {
            cur += nums[(i - 1) % n] * (n - 1);
            cur -= sum[i - 1] - sum[i - n];
            if (cur > ans) {
                ans = cur;
            }
        }
        return ans;
    }
}
//
//作者：AC_OIer
//链接：https://leetcode-cn.com/problems/rotate-function/solution/by-ac_oier-sxbi/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

//前缀和 + 滑动窗口
//为了方便，我们将 nums 的长度记为 n。
//题目要对「旋转数组」做逻辑，容易想到将 nums 进行复制拼接，得到长度为 2 * n 的新数组，
//在新数组上任意一个长度为 n 的滑动窗口都对应了一个旋转数组。
//然后考虑在窗口的滑动过程中，计算结果会如何变化，
//假设当前我们处理到下标为 [i, i + n - 1] 的滑动窗口，根据题意，当前结果为：
//cur = nums[i] * 0 + nums[i + 1] * 1 + ... + nums[i + n - 1] * (n - 1)
//当窗口往后移动一位，也就是窗口的右端点来到 i + n 的位置，左端点来到 i + 1 的位置。
//我们需要增加「新右端点」的值，即增加 nums[i + n] * (n - 1)，
//同时减去「旧左端点」的值，即减少 nums[i] * 0（固定为 00），
//然后更新新旧窗口的公共部分 [i + 1, i + n - 1]。
//不难发现，随着窗口的逐步右移，每一位公共部分的权值系数都会进行减一。
//nums[i + 1] * 1 + nums[i + 2] * 2 + ... + nums[i + n - 1] * (n - 1)
//变为
//nums[i + 1] * 0 + nums[i + 2] * 1 + ... + nums[i + n - 1] * (n - 2)
//因此，公共部分的差值为 \sum_{idx = i + 1}^{i + n - 1}nums[idx]∑
//idx=i+1
//i+n−1
// nums[idx]，这引导我们可以使用前缀和进行优化。
//至此，我们从旧窗口到新窗口的过渡，都是 O(1)，整体复杂度为 O(n)。
//实现上，我们并不需要真正对 nums 进行复制拼接，
// 而只需要在计算前缀和数组 sum 进行简单的下标处理即可。
//作者：AC_OIer
//链接：https://leetcode-cn.com/problems/rotate-function/solution/by-ac_oier-sxbi/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

//找规律就好了 以示例一为例 因为是顺时针转动，所以所有的可能性分别为
//
//4×0+3×1+2×2+6×3
//4×1+3×2+2×3+6×0
//4×2+3×3+2×0+6×1
//4×3+3×0+2×1+6×2
//可以发现，每次转动都是：除了0处于的位置外，其余的位置与上一次转动的结果相比都是增加了一次。
//假设当前为0的下标为index，数组元素和为sum，
//数组与下标乘积之和为cnt，每次转动的结果为 cnt = cnt - sum + num[index]*num.length;
//
//class Solution {
//    public int maxRotateFunction(int[] nums) {
//        int len = nums.length;
//        int cnt = 0;
//        int sum = 0;
//        for(int i=0;i<len;i++)
//        {
//            sum = sum + nums[i];
//            cnt = cnt + i * nums[i];
//        }
//        // System.out.println(0+" "+cnt);
//        int max = cnt;
//        for(int i=len-1;i>0;i--)
//        {
//            cnt = cnt + sum - nums[i] * len;
//            // System.out.println(i+" "+cnt);
//            max = Math.max(max,cnt);
//        }
//        return max;
//
//    }
//}
